home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / pascal / jdbtree.com / JDBTREE.DOC < prev    next >
Encoding:
Text File  |  1991-06-07  |  8.6 KB  |  289 lines
  1.  
  2.  
  3.             File:  JDBTREE
  4.           Author:  Jeffrey L. Darling
  5. Date established:  02-17-1991
  6.   Latest release:  06-04-1991
  7.  Current Version:  1.20
  8. =======================================================================
  9.  
  10.  
  11.  
  12.                             CONTENTS
  13.  
  14.                      I.  Archive file list
  15.                     II.  System requirements
  16.                    III.  Purpose
  17.                     IV.  Brief Description
  18.                      V.  Detailed Description
  19.                     VI.  Version Information
  20.                    VII.  Authors Contact information
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  I. Archive file list:
  29. -----------------------------------------------------------------------
  30.  
  31. JDBTREE  DOC     8609   6-07-91  12:38a   This Documentation
  32. JDBTREE  EXE     7248   6-01-91   4:35a   Executable
  33. WORDS    DAT       84   6-01-91   4:35a   Data file - JDBTREE.EXE
  34. JDBTREE  PAS     3723   6-01-91   4:35a   Pascal Program
  35. CUST     EXE     6736   6-07-91  12:35p   Executable
  36. CUST     DOC     3136   6-07-91  12:35p   Cust Documentation
  37. CUST     DAT       65   6-07-91  12:35p   Data file - CUST.EXE
  38. CUST     PAS     3463   6-07-91  12:35p   Pascal Program
  39.  
  40. If any of these files are not as shown above, Please contact the author.
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51. II. System requirements:
  52. -----------------------------------------------------------------------
  53.    IBM PC,XT,AT,PS/2 or compatible.
  54.    256K RAM
  55.    Turbo Pascal 5.5
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74. III. Purpose:
  75. -----------------------------------------------------------------------
  76.  
  77. This Turbo Pascal program demonstrates how to use Binary trees
  78.  
  79. A binary tree is a data structure.  It is a very useful structure to
  80. learn.  If you are in a Computer Science program, I am sure this
  81. will be helpful to you. In this package I will attempt to explain
  82. this mysterious data structure.
  83.  
  84. If you REALLY want to understand this data structure, then follow
  85. the instructions below.
  86.  
  87. 1.  Load JDBTREE.PAS into TURBO PASCAL using INTEGRATED ENVIRONMENT.
  88.  
  89. 2.  Use the "Watch Variable" capabilities on the following variables
  90.     in this format:
  91.  
  92.                 Ancestor
  93.                 Root
  94.                 Ancestor^,R
  95.                 Root^,R
  96.                 NextWord
  97.  
  98.     Watch them! keep track of what is happening with each and
  99.     every variable. ESPECIALLY the RIGHT and LEFT variables.
  100.     You will see that the RIGHT and LEFT occur next to Ancestor^,R
  101.     and Root^,R. The R is a Debug expression format character for
  102.     displaying the field names of a record.
  103.  
  104. 3.  Use the "Trace" capabilities! In conjunction with the
  105.     "Watch Variable" option. You will see how it really works.
  106.     Pressing F7 will execute One line at a time.
  107.     (Step Through the program)
  108.  
  109.  
  110. 4.  Change the WORDS.DAT file.  Put in values of your own. Then
  111.     try to predict what will happen in each and every variable.
  112.     This will force you to think about HOW it works.  Think about
  113.     every tiny detail. Be creative, Notice things that are side
  114.     effects and how you can use these side effects in programs that
  115.     YOU write.
  116.  
  117. Believe me, just try it. I think you will be surprised with
  118. the results.  Especially if you are a novice programmer.
  119.  
  120.  
  121.  
  122. IV. Brief Description:
  123. -----------------------------------------------------------------------
  124.  
  125. In this program, each node on the tree contains a name and an
  126. integer number telling how many times that name has been read
  127. in from the WORDS.DAT text file. Also notice that the names have
  128. been sorted as well! This is a side affect of binary trees.
  129.  
  130. Each time a NEW name is read in, then it is put in the proper
  131. place in the tree. If the name is NOT NEW then it's counter is
  132. accumulated.
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
  145. V. Detailed Description:
  146. -----------------------------------------------------------------------
  147.  
  148. Every binary tree must contain at least four elements.
  149.  
  150.    One: the info you wish to store.
  151.    Two: a pointer to the LEFT NODE.
  152.  Three: a pointer to the RIGHT NODE.
  153.   Four: a record to point.
  154.  
  155.  Note: NODES are sometimes referred to as LINKS. Do not confuse binary
  156.        trees with linked lists, because they are very different.
  157.  
  158.  
  159.  
  160.    type String_10 = String[10];
  161.         Branch=^Treenode;
  162.         Treenode = record
  163.           Word : String_10;
  164.           count : integer;
  165.           Left,Right : Branch
  166.         end; {Tree}
  167.  
  168.  
  169. Above is the type declaration for the binary tree.
  170.  
  171.  
  172.          Variable       Eplanation
  173.          --------       --------------------------
  174.          String_10      Declares a string type with a length of 10
  175.                         The input record contains a list of names.
  176.                         Each unique name is stored in a variable
  177.                         called Word.
  178.  
  179.          Branch         Pointer to Treenode
  180.                         This pointer type is VERY important. This will
  181.                         be the type of pointer of the Left and Right
  182.                         pointers to the Trees NODES. Branch must be
  183.                         declared as a pointer of the record that the
  184.                         node is declared as. In this case Treenode.
  185.  
  186.          Treenode       This record contains the four essential elements
  187.                         of the tree structure.
  188.  
  189.          Word           Contains string of 10 characters.
  190.                         This is information that we wish to store.
  191.  
  192.          Count          Contains integer with a count of how many
  193.                         times the Word occurs in the input file.
  194.                         This is also valuable information we wish to
  195.                         store.
  196.  
  197.          Left           Pointer to Left Treenode
  198.  
  199.          Right          Pointer to Right Treenode
  200.  
  201.  
  202.  
  203.  
  204. Another important element of the tree structure is the ROOT.
  205.  
  206.  
  207.                                 Root                                           
  208.                        ┌────┬─────┬────┬─────┐                                 
  209.                        │Word│count│Left│Right│                                 
  210.                        └────┴─────┴────┴─────┘
  211.                         Jeff   2
  212. ┌──────┐                             │    │
  213.       └─────────────────────────────┘    │                                    
  214. ┌────┬─────┬────┬─────┐                   │  ┌────┬─────┬────┬─────┐           
  215. │Word│count│Left│Right│                   └ │Word│count│Left│Right│           
  216. └────┴─────┴────┴─────┘                      └────┴─────┴────┴─────┘           
  217. Debbie  1    nil   nil                        Kim    10   nil
  218.                                                                 │
  219.                               ┌─────────────────────────────────┘
  220.                               
  221.                               ┌────┬─────┬────┬─────┐
  222.                               │Word│count│Left│Right│
  223.                               └────┴─────┴────┴─────┘
  224.                               Laura   1    nil   │
  225.                                                  │
  226.                                                  │
  227.                                                  │  ┌────┬─────┬────┬─────┐
  228.                                                  └ │Word│count│Left│Right│
  229.                                                     └────┴─────┴────┴─────┘
  230.                                                     Steve   1    nil  nil
  231.  
  232.  
  233.  
  234.  
  235.  
  236.  
  237.  
  238. VI. Version Information
  239. -----------------------------------------------------------------------
  240.  
  241.  1.00 Initial release 03-17-1991
  242.  
  243.      No documentation.  Originally a simple solution to a problem
  244.      stated in a message base of a bulletin board.  I wish I could
  245.      remember the fellows name so I can give him credit for
  246.      motivating me to do this.
  247.  
  248.  1.10 Trivial update  04-09-1991
  249.  
  250.      Added file handling so data was supplied to give users a good
  251.      pool of data.
  252.  
  253.  
  254.  1.20 Added some documentation  06-04-1991
  255.  
  256.      Added all of the JDBTREE.DOC file.
  257.      Includes some in code documentation.
  258.  
  259.  1.30 Added CUST program 6-07-1991
  260.  
  261.      Added CUST.PAS, CUST.DOC. CUST.DAT and CUST.EXE
  262.      This program uses the same code as JDBTREE to implement
  263.      the use of files with the seek procedure.
  264.  
  265.  
  266.  
  267.  
  268.  
  269.  
  270. VII.  Authors Contact information
  271. -----------------------------------------------------------------------
  272.  
  273.       If you have any suggestions, questions or comments feel free
  274.       to contact me.
  275.  
  276.         U.S. MAIL:    Jeff Darling
  277.                       P.O. Box 154
  278.                       Barrington Il, 60011
  279.  
  280.         Email:        Jeff Darling
  281.                       Polysyncronism BBS
  282.                       (708) 358-5104
  283.                       24 hours 300/1200/2400 8N1
  284.  
  285.         CompuServe:   Jeff Darling 72010,22
  286.  
  287.  
  288.  
  289.